#include <atomic>
#include <memory>

template <typename T>
class LockFreeQueue 
{
private:
    struct Node 
    {
        T data;
        Node* next;
        Node(const T& value) : data(value), next(nullptr) {}
    };

    std::atomic<Node*> head;
    std::atomic<Node*> tail;

public:
    LockFreeQueue() : head(new Node(T())), tail(head.load()) {}  // 哨兵节点

    ~LockFreeQueue() 
    {
        while (Node* node = head.load()) 
        {
            head.store(node->next);
            delete node;
        }
    }

    void push(const T& value) 
    {
        Node* newNode = new Node(value);
        while (true) 
        {
            Node* currentTail = tail.load();
            Node* next = currentTail->next.load();

            // 如果 tail 的 next 不为空，说明其他线程已经更新了 tail，帮助推进 tail
            if (currentTail != tail.load()) continue;

            // 尝试将新节点链接到尾节点
            if (next == nullptr) 
            {
                if (currentTail->next.compare_exchange_weak(next, newNode)) 
                {
                    // CAS 成功，尝试推进 tail
                    tail.compare_exchange_weak(currentTail, newNode);
                    return;
                }
            }
            else 
            {
                // 如果 next 不为空，帮助推进 tail
                tail.compare_exchange_weak(currentTail, next);
            }
        }
    }

    bool pop(T& value)
    {
        while (true) 
        {
            Node* currentHead = head.load();
            Node* currentTail = tail.load();
            Node* next = currentHead->next.load();

            // 如果 head == tail，队列为空
            if (currentHead == currentTail)
            {
                if (next == nullptr) 
                    return false;
                // 帮助推进 tail
                tail.compare_exchange_weak(currentTail, next);
            }
            else 
            {
                // 尝试移动 head
                if (head.compare_exchange_weak(currentHead, next)) 
                {
                    value = next->data;
                    delete currentHead;  // 释放旧头节点
                    return true;
                }
            }
        }
    }
};